package com.gitee.ywj1352.kaishi.数组和排序;

/**
 * @author wenjie.yang
 * @date 4/28/2020 3:41 PM
 */
public class 数组去重 {

    public static void main(String[] args) {
        int[] arr = {1, 2, 1, 3};
        int[] ints = singleNumbers(arr);
        System.out.println(ints[0]);
        System.out.println(ints[1]);
    }

    /**
     * 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
     * 输入：nums = [4,1,4,6]
     * 输出：[1,6] 或 [6,1]
     *
     * @param nums
     * @return
     */
    public static int[] singleNumbers(int[] nums) {
        //用于将所有的数异或起来
        int k = 0;
        for (int num : nums) {
            k ^= num;
        }
        /**
         * 5 :  101
         * 3 :  011
         * m :  110
         * 所有找到 m 的最低位为1 的 操作就是 找到 不相同 数字的 第一个 不相同的位置
         * 5 & 2 : 101 & 010 = 0 == 0
         * 3 & 2 : 011 & 010 = 2 != 0
         */
        //获得k中最低位的1
        int mask = 1;
        //mask = k & (-k) 这种方法也可以得到mask，具体原因百度 哈哈哈哈哈
        while ((k & mask) == 0) {
            mask <<= 1;
        }
        int a = 0;
        int b = 0;
        for (int num : nums) {

            if ((num & mask) == 0) {
                a ^= num;
            } else {
                b ^= num;
            }
        }
        return new int[]{a, b};
    }

}
